package com.liunian.algorithmstudy.backtracking.combine;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinations17 {

	/**
	 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

	 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
	 */
	List<String> res = new ArrayList<>();
	StringBuilder path = new StringBuilder();
	Map<String, String> map = new HashMap<>();

	public List<String> letterCombinations(String digits) {
		if (digits.length() == 0) {
			return res;
		}
		map.put("2", "abc");
		map.put("3", "def");
		map.put("4", "ghi");
		map.put("5", "jkl");
		map.put("6", "mno");
		map.put("7", "pqrs");
		map.put("8", "tuv");
		map.put("9", "wxyz");
		backTracking(digits, 0);
		return res;
	}

	private void backTracking(String digits, int index) {
		if (path.length() == digits.length()) {
			res.add(path.toString());
			return;
		}
		String value = String.valueOf(digits.charAt(index));
		for (int i = 0; i < map.get(value).length(); i++) {
			path.append(map.get(value).charAt(i));
			backTracking(digits, index + 1);
			path.deleteCharAt(path.length() - 1);
		}
	}

	public static void main(String[] args) {
		LetterCombinations17 test = new LetterCombinations17();
		System.out.println(test.letterCombinations(""));
	}

}
